#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> g(2, vector<vector<int>>(n));
        for (auto& it : redEdges) {
            g[0][it[0]].push_back(it[1]);
        }
        for (auto& it : blueEdges) {
            g[1][it[0]].push_back(it[1]);
        }
        vector<int> ans(n, -1);
        queue<PII>q;
        q.push({ 0,0 });
        q.push({ 0,1 });
        bool st[n][2];
        memset(st, false, sizeof st);
        int d = 0;
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                auto it = q.front();
                q.pop();
                int a = it.first;
                int b = it.second;
                //cout<<a<<" "<<b<<endl;
                if (ans[a] == -1) {
                    //  cout<<ans[a]<<"--"<<a<<" "<<d<<endl;
                    ans[a] = d;
                }
                st[a][b] = true;
                int c = b ^ 1;

                for (auto j : g[c][a]) {
                    //  if(st[j][c])continue;
                    if (!st[j][c]) {
                        //   cout<<j<<endl;
                        q.push({ j,c });
                    }
                }
            }
            d++;
            // cout<<"ddd=="<<d<<endl;
        }

        return ans;
    }
};